Biological complex network motifs discovery, based on theoretical research of complex networks, is an important method for studying biological networks, which provides a new perspective on life phenomena and life mechanisms. However, it computes inefficiently when dealing with large networks or mining big motifs. On the basis of existing serial ESU (Enumerate SUbgraph) algorithm of network motifs discovery, a parallelized ESU algorithm based on Message Passing Interface (MPI) was proposed. The node values in ESU algorithm were optimized to solve the problem of node value dependency, the number of subgraphs was counted by using subgraph discovery strategy of ESU algorithm, and a dynamic programming method was used to determine optimal node allocation strategy to satisfy load balancing. The experiments on simulated and biological networks show that the parallelized ESU algorithm addresses node value dependency and realizes a load balancing strategy, which saves more than 90% running time compared to serial algorithm. Furthermore, the parallel algorithm is suitable for different types and different scales of networks, and effectively improves computation efficiency of network motifs discovery.

Markov Clustering Algorithm (MCL) is an effective method to find modules in large-scale biological networks. It can mine modules that have significant influence on network structure and function. The algorithm involves large-scale matrix calculations, so its complexity can reach cubic orders. For the problem of high complexity, a parallel algorithm of Markov clustering based on Message Passing Interface (MPI) was proposed to improve computational performance of algorithm. Firstly, a biological network was transformed into an adjacency matrix. Secondly, according to the characteristics of the algorithm, the matrix size was judged and a new matrix was regenerated to handle the calculation of non-square multiple matrix. Thirdly, the algorithm was calculated in parallel by means of block allocation, which could effectively implement the operation of matrix of any size. Finally, the loop was parallelized until the matrix was converged to obtain network clustering results. The experimental results on simulated network and real biological network datasets show that compared with Full-block Collective Communication (FCC) parallel method, the average parallel efficiency is improved by more than 10 percentage points, so the optimization algorithm can be applied in different types of large-scale biological networks.